package 蓝桥杯.算法板子.数学;

import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

/**
 * @Title: 分解质因数
 * @Author 贾金博
 * @Package 蓝桥杯.算法板子.数学
 * @Date 2024/4/12 19:52
 * @description:
 */
public class 分解质因数 {
    public static FastReader sc = new FastReader();
    public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));


    public static void main(String[] args) {

        Long n = sc.nextLong();
        while(n -- != 0 ) {
            Map<Long, Long>mp = new HashMap<>();
            Set<Long> se = new TreeSet<>();

            Long x = sc.nextLong();
            for(Long i = 2l; i * i <= x; ++ i ) {
                if(x % i == 0) {
                    Long t = 0l;
                    while(x % i == 0) {
                        x /= i;
                        t ++;
                    }
                    //out.println("i = " + i + " t = " + t);
                    se.add(i);
                    mp.merge(i, t, Long::sum);
                }
            }
            if(x > 1) {
                se.add(x);
                mp.merge(x, 1l, Long::sum);
            }
            for(Long i : se) {
                out.print(i + " " + mp.get(i) + "\n");
            }
            out.println();
            out.flush();
        }
    }
}
